/*
 * (C) Copyright 2014-2019, by Dimitrios Michail
 *
 * JHeaps Library
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.jheaps.array

import org.jheaps.AddressableHeap
import org.jheaps.annotations.LinearTime
import java.io.Serializable
import java.lang.IllegalArgumentException

/**
 * An array based d-ary addressable heap. The heap is sorted according to the
 * [natural ordering][Comparable] of its keys, or by a
 * [Comparator] provided at heap creation time, depending on which
 * constructor is used.
 *
 *
 *
 * The implementation uses an array in order to store the elements. and
 * automatically maintains the size of the array much like a
 * [java.util.Vector] does, providing amortized O(log_d(n)) time cost for
 * the `insert` and amortized O(d log_d(n)) for the `deleteMin`
 * operation. Operation `findMin`, is a worst-case O(1) operation.
 * Operations `delete` and `decreaseKey` take worst-case O(log(n))
 * time. The bounds are worst-case if the user initializes the heap with a
 * capacity larger or equal to the total number of elements that are going to be
 * inserted into the heap.
 *
 *
 *
 * Constructing such a heap from an array of elements can be performed using the
 * method [.heapify] or
 * [.heapify] in linear time.
 *
 *
 *
 * Note that the ordering maintained by a d-ary heap, like any heap, and whether
 * or not an explicit comparator is provided, must be *consistent with
 * `equals`* if this heap is to correctly implement the `Heap`
 * interface. (See `Comparable` or `Comparator` for a precise
 * definition of *consistent with equals*.) This is so because the
 * `Heap` interface is defined in terms of the `equals` operation,
 * but a binary heap performs all key comparisons using its `compareTo`
 * (or `compare`) method, so two keys that are deemed equal by this method
 * are, from the standpoint of the d-ary heap, equal. The behavior of a heap
 * *is* well-defined even if its ordering is inconsistent with
 * `equals`; it just fails to obey the general contract of the
 * `Heap` interface.
 *
 *
 *
 * **Note that this implementation is not synchronized.** If
 * multiple threads access a heap concurrently, and at least one of the threads
 * modifies the heap structurally, it *must* be synchronized externally.
 * (A structural modification is any operation that adds or deletes one or more
 * elements or changing the key of some element.) This is typically accomplished
 * by synchronizing on some object that naturally encapsulates the heap.
 *
 * @param <K>
 * the type of keys maintained by this heap
 * @param <V>
 * the type of values maintained by this heap
 *
 * @author Dimitrios Michail
</V></K> */
class DaryArrayAddressableHeap<K, V> @JvmOverloads constructor(
    d: Int,
    comparator: Comparator<in K?>? = null,
    capacity: Int = DEFAULT_HEAP_CAPACITY
) : AbstractArrayAddressableHeap<K, V>(comparator, capacity), Serializable {
    /**
     * Degree
     */
    protected var d: Int

    /**
     * Constructs a new, empty heap, with a provided initial capacity using the
     * natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param d
     * the number of children of each node in the d-ary heap
     * @param capacity
     * the initial heap capacity
     * @throws IllegalArgumentException
     * in case the number of children per node are less than 2
     */
    constructor(d: Int, capacity: Int) : this(d, null, capacity)

    /**
     * Constructs a new, empty heap, with a provided initial capacity ordered
     * according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is provided by the user and is adjusted
     * automatically based on the sequence of insertions and deletions. The
     * capacity will never become smaller than the initial requested capacity.
     *
     * @param d
     * the number of children of each node in the d-ary heap
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     * @param capacity
     * the initial heap capacity
     * @throws IllegalArgumentException
     * in case the number of children per node are less than 2
     */
    /**
     * Constructs a new, empty heap, using the natural ordering of its keys.
     *
     *
     *
     * All keys inserted into the heap must implement the [Comparable]
     * interface. Furthermore, all such keys must be *mutually
     * comparable*: `k1.compareTo(k2)` must not throw a
     * `ClassCastException` for any keys `k1` and `k2` in the
     * heap. If the user attempts to put a key into the heap that violates this
     * constraint (for example, the user attempts to put a string key into a
     * heap whose keys are integers), the `insert(Object key)` call will
     * throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
     * adjusts automatically based on the sequence of insertions and deletions.
     *
     * @param d
     * the number of children of each node in the d-ary heap
     * @throws IllegalArgumentException
     * in case the number of children per node are less than 2
     */
    /**
     * Constructs a new, empty heap, ordered according to the given comparator.
     *
     *
     *
     * All keys inserted into the heap must be *mutually comparable* by
     * the given comparator: `comparator.compare(k1,
     * k2)` must not throw a `ClassCastException` for any keys `k1`
     * and `k2` in the heap. If the user attempts to put a key into the
     * heap that violates this constraint, the `insert(Object key)` call
     * will throw a `ClassCastException`.
     *
     *
     *
     * The initial capacity of the heap is [.DEFAULT_HEAP_CAPACITY] and
     * adjusts automatically based on the sequence of insertions and deletions.
     *
     * @param d
     * the number of children of each node in the d-ary heap
     * @param comparator
     * the comparator that will be used to order this heap. If
     * `null`, the [natural ordering][Comparable] of
     * the keys will be used.
     * @throws IllegalArgumentException
     * in case the number of children per node are less than 2 *
     */
    init {
        if (d < 2) {
            throw IllegalArgumentException(D_ARY_HEAPS_MUST_HAVE_AT_LEAST_2_CHILDREN_PER_NODE)
        }
        this.d = d
    }

    /**
     * Get an iterator for all handles currently in the heap.
     *
     * This method is especially useful when building a heap using the heapify
     * method. Unspecified behavior will occur if the heap is modified while
     * using this iterator.
     *
     * @return an iterator which will return all handles of the heap
     */
    fun handlesIterator(): Iterator<ArrayHandle> {
        return object : MutableIterator<ArrayHandle> {
            private var pos: Int = 1

            override fun hasNext(): Boolean {
                return pos <= size
            }

            override fun next(): AbstractArrayAddressableHeap<K,V>.ArrayHandle {
                if (pos > size) {
                    throw NoSuchElementException()
                }
                return array[pos++]!!
            }

            override fun remove() {
                throw UnsupportedOperationException()
            }
        }
    }

    /**
     * Ensure that the array representation has the necessary capacity.
     *
     * @param capacity
     * the requested capacity
     */
    override fun ensureCapacity(capacity: Int) {
        checkCapacity(capacity)
        /*val newArray: Array<ArrayHandle> = java.lang.reflect.Array.newInstance(
            ArrayHandle::class.java, capacity + 1
        ) as Array<ArrayHandle>*/
        val newArray = arrayOfNulls<ArrayHandle>(capacity + 1)
        System.arraycopy(array, 1, newArray, 1, size)
        array = newArray
    }

    override fun forceFixup(k: Int) {
        var k: Int = k
        val h: ArrayHandle = array[k]!!
        while (k > 1) {
            val p: Int = (k - 2) / d + 1
            array[k] = array[p]
            array[k]!!.index = k
            k = p
        }
        array[k] = h
        h.index = k
    }

    override fun fixup(k: Int) {
        var k: Int = k
        val h: ArrayHandle = array[k]!!
        while (k > 1) {
            val p: Int = (k - 2) / d + 1
            if ((array[p]!!.key as Comparable<K>).compareTo(h.key) <= 0) {
                break
            }
            array[k] = array[p]
            array[k]!!.index = k
            k = p
        }
        array[k] = h
        h.index = k
    }

    override fun fixupWithComparator(k: Int) {
        var k: Int = k
        val h: ArrayHandle = array[k]!!
        while (k > 1) {
            val p: Int = (k - 2) / d + 1
            if (comparator!!.compare(array[p]!!.key, h.key) <= 0) {
                break
            }
            array[k] = array[p]
            array[k]!!.index = k
            k = p
        }
        array[k] = h
        h.index = k
    }

    override fun fixdown(k: Int) {
        var k: Int = k
        var c: Int
        val h: ArrayHandle = array[k]!!
        while (((d * (k - 1) + 2).also { c = it }) <= size) {
            var maxc: Int = c
            var i: Int = 1
            while (i < d && c + i <= size) {
                if ((array[maxc]!!.key as Comparable<K>).compareTo(array[c + i]!!.key) > 0) {
                    maxc = c + i
                }
                i++
            }
            if ((h.key as Comparable<K>).compareTo(array[maxc]!!.key) <= 0) {
                break
            }
            array[k] = array[maxc]
            array[k]!!.index = k
            k = maxc
        }
        array[k] = h
        h.index = k
    }

    override fun fixdownWithComparator(k: Int) {
        var k: Int = k
        var c: Int
        val h: ArrayHandle = array[k]!!
        while (((d * (k - 1) + 2).also { c = it }) <= size) {
            var maxc: Int = c
            var i: Int = 1
            while (i < d && c + i <= size) {
                if (comparator!!.compare(array[maxc]!!.key, array[c + i]!!.key) > 0) {
                    maxc = c + i
                }
                i++
            }
            if (comparator!!.compare(h.key, array[maxc]!!.key) <= 0) {
                break
            }
            array[k] = array[maxc]
            array[k]!!.index = k
            k = maxc
        }
        array[k] = h
        h.index = k
    }

    companion object {
        private val serialVersionUID: Long = 1

        private val D_ARY_HEAPS_MUST_HAVE_AT_LEAST_2_CHILDREN_PER_NODE: String =
            "D-ary heaps must have at least 2 children per node"

        /**
         * Default initial capacity of the binary heap.
         */
        val DEFAULT_HEAP_CAPACITY: Int = 16

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param <V>
         * the type of values maintained by the heap
         * @param d
         * the number of children of the d-ary heap
         * @param keys
         * an array of keys
         * @param values
         * an array of values, can be null
         * @return a d-ary heap
         * @throws IllegalArgumentException
         * in case the number of children per node are less than 2
         * @throws IllegalArgumentException
         * in case the keys array is null
         * @throws IllegalArgumentException
         * in case the values array has different length than the keys
         * array
        </V></K> */
        @JvmStatic
        @LinearTime
        fun <K, V> heapify(d: Int, keys: Array<K>?, values: Array<V>?): DaryArrayAddressableHeap<K, V> {
            if (d < 2) {
                throw IllegalArgumentException(D_ARY_HEAPS_MUST_HAVE_AT_LEAST_2_CHILDREN_PER_NODE)
            }
            if (keys == null) {
                throw IllegalArgumentException("Key array cannot be null")
            }
            if (values != null && keys.size != values.size) {
                throw IllegalArgumentException("Values array must have the same length as the keys array")
            }
            if (keys.isEmpty()) {
                return DaryArrayAddressableHeap(d)
            }

            val h: DaryArrayAddressableHeap<K, V> = DaryArrayAddressableHeap(d, keys.size)

            for (i in keys.indices) {
                val key: K = keys.get(i)
                val value: V? = if ((values == null)) null else values[i]
                val ah = h.ArrayHandle(key, value)
                ah.index = i + 1
                h.array[i + 1] = ah
            }
            h.size = keys.size

            for (i in keys.size / d downTo 1) {
                h.fixdown(i)
            }

            return h
        }

        /**
         * Create a heap from an array of elements. The elements of the array are
         * not destroyed. The method has linear time complexity.
         *
         * @param <K>
         * the type of keys maintained by the heap
         * @param <V>
         * the type of values maintained by the heap
         * @param d
         * the number of children of the d-ary heap
         * @param keys
         * an array of keys
         * @param values
         * an array of values, can be null
         * @param comparator
         * the comparator to use
         * @return a d-ary heap
         * @throws IllegalArgumentException
         * in case the number of children per node are less than 2
         * @throws IllegalArgumentException
         * in case the keys array is null
         * @throws IllegalArgumentException
         * in case the values array has different length than the keys
         * array
        </V></K> */
        @LinearTime
        fun <K, V> heapify(
            d: Int, keys: Array<K>?, values: Array<V>?,
            comparator: Comparator<in K?>?
        ): DaryArrayAddressableHeap<K, V> {
            if (d < 2) {
                throw IllegalArgumentException(D_ARY_HEAPS_MUST_HAVE_AT_LEAST_2_CHILDREN_PER_NODE)
            }
            if (keys == null) {
                throw IllegalArgumentException("Keys array cannot be null")
            }
            if (values != null && keys.size != values.size) {
                throw IllegalArgumentException("Values array must have the same length as the keys array")
            }
            if (keys.isEmpty()) {
                return DaryArrayAddressableHeap(d, comparator)
            }

            val h: DaryArrayAddressableHeap<K, V> = DaryArrayAddressableHeap(d, comparator, keys.size)

            for (i in keys.indices) {
                val key: K = keys[i]
                val value: V? = if ((values == null)) null else values[i]
                val ah = h.ArrayHandle(key, value)
                ah.index = i + 1
                h.array[i + 1] = ah
            }
            h.size = keys.size

            for (i in keys.size / d downTo 1) {
                h.fixdownWithComparator(i)
            }

            return h
        }
    }
}
